{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Spiral Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: spiralOrder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #螺旋矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>m</code> 行 <code>n</code> 列的矩阵 <code>matrix</code> ，请按照 <strong>顺时针螺旋顺序</strong> ，返回矩阵中的所有元素。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/13/spiral1.jpg\" style=\"width: 242px; height: 242px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[1,2,3],[4,5,6],[7,8,9]]\n",
    "<strong>输出：</strong>[1,2,3,6,9,8,7,4,5]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/13/spiral.jpg\" style=\"width: 322px; height: 242px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]\n",
    "<strong>输出：</strong>[1,2,3,4,8,12,11,10,9,5,6,7]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == matrix.length</code></li>\n",
    "\t<li><code>n == matrix[i].length</code></li>\n",
    "\t<li><code>1 <= m, n <= 10</code></li>\n",
    "\t<li><code>-100 <= matrix[i][j] <= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [spiral-matrix](https://leetcode.cn/problems/spiral-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [spiral-matrix](https://leetcode.cn/problems/spiral-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3],[4,5,6],[7,8,9]]', '[[1,2,3,4],[5,6,7,8],[9,10,11,12]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        l = 0\n",
    "        r = n - 1\n",
    "        b = m - 1\n",
    "        t = 0\n",
    "        res = []\n",
    "        while l <= r and t <= b:\n",
    "            for i in range(l, r+1):\n",
    "                res.append(matrix[t][i])\n",
    "            t += 1\n",
    "            for i in range(t, b+1):\n",
    "                res.append(matrix[i][r])\n",
    "            r -= 1\n",
    "            for i in range(r, l-1, -1):\n",
    "                res.append(matrix[b][i])\n",
    "            b -= 1\n",
    "            for i in range(b, t-1, -1):\n",
    "                res.append(matrix[i][l])\n",
    "            l += 1\n",
    "        return res[:m*n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        out = []\n",
    "        while 1:\n",
    "            # print(out)\n",
    "            try:\n",
    "                out.extend(matrix.pop(0))\n",
    "                # print(matrix)\n",
    "                i = 0\n",
    "                while i<len(matrix)-1:\n",
    "                    out.append(matrix[i].pop(-1))\n",
    "                    i+=1\n",
    "                # print(matrix)\n",
    "                out.extend(matrix.pop(-1)[::-1])\n",
    "                # print(matrix)\n",
    "                i = len(matrix)-1\n",
    "                while i>0:\n",
    "                    out.append(matrix[i].pop(0))\n",
    "                    i-=1\n",
    "            except:\n",
    "                break\n",
    "            # print(matrix)\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not matrix or not matrix[0]:\n",
    "            return []\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        l, t, r, b = 0, 0, n - 1, m - 1\n",
    "        res = []\n",
    "        while l <= r and t <= b:\n",
    "            if l == r:\n",
    "                for i in range(t, b+1):\n",
    "                    res.append(matrix[i][l])\n",
    "            elif t == b:\n",
    "                for i in range(l, r+1):\n",
    "                    res.append(matrix[t][i])\n",
    "            else:\n",
    "                for i in range(l, r):\n",
    "                    res.append(matrix[t][i])\n",
    "                for i in range(t, b):\n",
    "                    res.append(matrix[i][r])\n",
    "                for i in range(r, l, -1):\n",
    "                    res.append(matrix[b][i])\n",
    "                for i in range(b, t, -1):\n",
    "                    res.append(matrix[i][l])\n",
    "            l, t, r, b = l + 1, t + 1, r - 1, b - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if len(matrix) == 0:\n",
    "            return []\n",
    "        matrix_row, matrix_col = len(matrix), len(matrix[0])\n",
    "        # 定义一个维度和matrix相同的全0矩阵，用于找到点移动的路线；0代表可以通过，1代表不能通过\n",
    "        detect_matrix = []\n",
    "        for _ in range(matrix_row):\n",
    "            detect_matrix.append([0]*matrix_col)\n",
    "        # 定义点移动的方向集合，先后顺序代表优先级，题目要求顺时针旋转\n",
    "        move_direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        # 定义移动点的初始位置\n",
    "        start_pos = [0, 0]\n",
    "        detect_matrix[0][0] = 1\n",
    "        # 定义保存最终结果的集合，初始元素就是起始值\n",
    "        final_matrix = [matrix[0][0]]\n",
    "        print(detect_matrix)\n",
    "\n",
    "        while True:\n",
    "            # 遍历检测矩阵，如果当前矩阵中没有0元素，说明原matrix矩阵已经遍历完成\n",
    "            for each_row in detect_matrix:\n",
    "                if 0 not in each_row:\n",
    "                    break\n",
    "            # 获取当前位置start_pos的可移动方向\n",
    "            next_direction = self.get_direction(start_pos, move_direction, detect_matrix)\n",
    "            print(\"next_direction\", next_direction)\n",
    "            # 如果当前位置不能移动了，说明原matrix矩阵已经遍历完成；反之则可按给定方向移动\n",
    "            if next_direction is not None:\n",
    "                # 获取当前位置start_pos按求得next_direction方向移动的下一个坐标位置\n",
    "                next_pos = start_pos.copy()\n",
    "                next_pos[0] += next_direction[0]\n",
    "                next_pos[1] += next_direction[1]\n",
    "                # 按照求得next_direction方向一直移动start_pos点，直到超出矩阵matrix的范围或者当前位置为1不可通过了\n",
    "                while True:\n",
    "                    print(\"next_pos\", next_pos)\n",
    "                    if next_pos[0] in range(matrix_row) and next_pos[1] in range(matrix_col) and detect_matrix[next_pos[0]][next_pos[1]] != 1:\n",
    "                        next_pos_copy = next_pos.copy()\n",
    "                        # 将符合要求遍历得到的点保存到final_matrix集合中\n",
    "                        final_matrix.append(matrix[next_pos_copy[0]][next_pos_copy[1]])\n",
    "                        # 当前点遍历了，将其设为1，表示其已经不能再遍历了\n",
    "                        detect_matrix[next_pos[0]][next_pos[1]] = 1\n",
    "                        # 继续按照给定方向遍历下一个坐标点\n",
    "                        next_pos[0] += next_direction[0]\n",
    "                        next_pos[1] += next_direction[1]\n",
    "                    # 如果当前位置不符合要求，则要回到上一步位置，准备切换方向继续遍历\n",
    "                    else:\n",
    "                        start_pos = next_pos.copy()\n",
    "                        start_pos[0] -= next_direction[0]\n",
    "                        start_pos[1] -= next_direction[1]\n",
    "                        break\n",
    "            else:\n",
    "                break\n",
    "        return final_matrix\n",
    "\n",
    "    def get_direction(self, start_pos, move_direction, detect_matrix):\n",
    "        # 按照给定的4个方向遍历，按照方向的先后顺序如果有哪个方向可通过，则立即返回该方向；反之，则返回None，说明没有方向可通过了\n",
    "        for direction in move_direction:\n",
    "            next_pos = start_pos.copy()\n",
    "            next_pos[0] += direction[0]\n",
    "            next_pos[1] += direction[1]\n",
    "            row, col = len(detect_matrix), len(detect_matrix[0])\n",
    "            if next_pos[0] in range(row) and next_pos[1] in range(col) and detect_matrix[next_pos[0]][next_pos[1]] != 1:\n",
    "                return direction\n",
    "        return None\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]\n",
    "    final_matrix = Solution().spiralOrder(matrix)\n",
    "    print(final_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not matrix:return []\n",
    "        self.re=[]\n",
    "        m,n=len(matrix)-1,len(matrix[0])-1\n",
    "        def spiral(t):\n",
    "            self.re+=[matrix[t][i] for i in range(t,n-t)]+[matrix[i][n-t] for i in range(t,m-t)]+[matrix[m-t][i] for i in range(n-t,t,-1)]+[matrix[i][t] for i in range(m-t,t,-1)]\n",
    "        for t in range(min((m+1)//2,(n+1)//2)):\n",
    "            spiral(t)\n",
    "        if m>=n and n%2==0:\n",
    "            self.re.extend([matrix[x][n//2] for x in range(n//2,m-n//2+1)])\n",
    "        elif m<n and m%2==0:\n",
    "            self.re.extend([matrix[m//2][x] for x in range(m//2,n-m//2+1)])\n",
    "        return self.re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not matrix:\n",
    "            return []\n",
    "        res = []\n",
    "        row, col = len(matrix), len(matrix[0])\n",
    "        rowtop, coleft, rowbot, colright = 0, 0, row-1, col - 1\n",
    "        while rowbot > rowtop and coleft < colright:\n",
    "            for i in range(coleft, colright):\n",
    "                res.append(matrix[rowtop][i])\n",
    "            for i in range(rowtop, rowbot):\n",
    "                res.append(matrix[i][colright])\n",
    "            for i in range(colright, coleft, -1):\n",
    "                res.append(matrix[rowbot][i])\n",
    "            for i in range(rowbot, rowtop, -1):\n",
    "                res.append(matrix[i][coleft])\n",
    "            rowtop += 1\n",
    "            rowbot -= 1\n",
    "            coleft += 1\n",
    "            colright -= 1\n",
    "        if rowtop == rowbot:\n",
    "            for i in range(coleft, colright+1):\n",
    "                res.append(matrix[rowtop][i])\n",
    "        elif coleft == colright:\n",
    "            for i in range(rowtop, rowbot+1):\n",
    "                res.append(matrix[i][coleft])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not matrix:\n",
    "            return []\n",
    "        res = []\n",
    "        row, col = len(matrix), len(matrix[0])\n",
    "        rowtop, coleft, rowbot, colright = 0, 0, row-1, col - 1\n",
    "        while rowbot > rowtop and coleft < colright:\n",
    "            for i in range(coleft, colright):\n",
    "                res.append(matrix[rowtop][i])\n",
    "            for i in range(rowtop, rowbot):\n",
    "                res.append(matrix[i][colright])\n",
    "            for i in range(colright, coleft, -1):\n",
    "                res.append(matrix[rowbot][i])\n",
    "            for i in range(rowbot, rowtop, -1):\n",
    "                res.append(matrix[i][coleft])\n",
    "            rowtop += 1\n",
    "            rowbot -= 1\n",
    "            coleft += 1\n",
    "            colright -= 1\n",
    "        if rowtop == rowbot:\n",
    "            for i in range(coleft, colright+1):\n",
    "                res.append(matrix[rowtop][i])\n",
    "        elif coleft == colright:\n",
    "            for i in range(rowtop, rowbot+1):\n",
    "                res.append(matrix[i][coleft])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not matrix:\n",
    "            return []\n",
    "        i, j = 0, 0\n",
    "        flag = 0\n",
    "        ilen = len(matrix[0])\n",
    "        jlen = len(matrix)\n",
    "        ileft, iright = 0, ilen - 1\n",
    "        jleft, jright = 0, jlen - 1\n",
    "        result = []\n",
    "\n",
    "        while len(result) < ilen * jlen:\n",
    "            result.append(matrix[j][i])\n",
    "\n",
    "            if flag % 4 == 0:\n",
    "                if i == iright:\n",
    "                    flag += 1\n",
    "                    j += 1\n",
    "                    jleft += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            elif flag % 4 == 1:\n",
    "                if j == jright:\n",
    "                    flag += 1\n",
    "                    i -= 1\n",
    "                    iright -= 1\n",
    "                else:\n",
    "                    j += 1\n",
    "            elif flag % 4 == 2:\n",
    "                if i == ileft:\n",
    "                    flag += 1\n",
    "                    j -= 1\n",
    "                    jright -= 1\n",
    "                else:\n",
    "                    i -= 1\n",
    "            else:\n",
    "                if j == jleft:\n",
    "                    flag += 1\n",
    "                    i += 1\n",
    "                    ileft += 1\n",
    "                else:\n",
    "                    j -= 1\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if len(matrix) == 0 :\n",
    "            return []\n",
    "\n",
    "        ret = self._spiral_order(matrix, 0, len(matrix), 0, len(matrix[0]))\n",
    "        return ret\n",
    "\n",
    "    def _spiral_order(self, matrix, start_row, end_row, start_col, end_col):\n",
    "\n",
    "        rows = end_row - start_row\n",
    "        cols = end_col - start_col\n",
    "\n",
    "        retlst = []\n",
    "\n",
    "        # 1x1 and 1x2\n",
    "        if rows == 0 or cols == 0:\n",
    "            return []\n",
    "\n",
    "        if rows == 1:\n",
    "            for col in range(start_col, end_col):\n",
    "                retlst.append(matrix[start_row][col])\n",
    "            return retlst\n",
    "\n",
    "        if cols == 1:\n",
    "            for row in range(start_row, end_row):\n",
    "                retlst.append(matrix[row][start_col])\n",
    "            return retlst\n",
    "\n",
    "        if cols == 2 and rows == 2:\n",
    "            return [matrix[start_row][start_col], matrix[start_row][start_col+1],\n",
    "                    matrix[start_row+1][start_col+1], matrix[start_row+1][start_col]]\n",
    "\n",
    "\n",
    "        # col ->\n",
    "        for col in range(start_col, end_col):\n",
    "            retlst.append(matrix[start_row][col])\n",
    "        for row in range(start_row+1, end_row):\n",
    "            retlst.append(matrix[row][col])\n",
    "        for col in range(1, end_col-start_col):\n",
    "            retlst.append(matrix[row][end_col-col- 1])\n",
    "        for row in range(2, end_row - start_row):\n",
    "            retlst.append(matrix[end_row - row][start_col])\n",
    "\n",
    "        retlst.extend(self._spiral_order(matrix, start_row+1, end_row-1, start_col+1, end_col-1))\n",
    "\n",
    "        return retlst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not matrix:\n",
    "            return []\n",
    "        row=len(matrix)\n",
    "        col=len(matrix[0]) if row else 0\n",
    "        start=0\n",
    "        res=[]\n",
    "        while row>start*2 and col>start*2:\n",
    "                self.show(matrix,row,col,start,res)\n",
    "                start+=1\n",
    "        return res\n",
    "    def show(self,matrix,row,col,start,res):\n",
    "        endX = col - 1 - start\n",
    "        endY = row - 1 - start\n",
    "        # 从左到右打印一行\n",
    "        for i in range(start, endX+1):\n",
    "            number = matrix[start][i]\n",
    "            res.append(number)\n",
    "            print(number, ' ', end='')\n",
    "\n",
    "        # 从上到下打印一行\n",
    "        if start < endY:\n",
    "            for i in range(start+1, endY+1):\n",
    "                number = matrix[i][endX]\n",
    "                res.append(number)\n",
    "                print(number, ' ', end='')\n",
    "\n",
    "        # 从右到左打印一行\n",
    "        if start < endX and start < endY:\n",
    "            for i in range(endX-1, start-1, -1):\n",
    "                number = matrix[endY][i]\n",
    "                res.append(number)\n",
    "                print(number, ' ', end='')\n",
    "\n",
    "        # 从下到上打印一行\n",
    "        if start < endX and start < endY-1:\n",
    "            for i in range(endY-1, start, -1):\n",
    "                number = matrix[i][start]\n",
    "                res.append(number)\n",
    "                print(number, ' ', end='')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix):\n",
    "        ret = []\n",
    "        while matrix:\n",
    "            ret += matrix.pop(0)\n",
    "            if matrix and matrix[0]:\n",
    "                for row in matrix:\n",
    "                    ret.append(row.pop())\n",
    "            if matrix:\n",
    "                ret += matrix.pop()[::-1]\n",
    "            if matrix and matrix[0]:\n",
    "                for row in matrix[::-1]:\n",
    "                    ret.append(row.pop(0))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        result = []\n",
    "        m = len(matrix)\n",
    "        n = 0\n",
    "        if m > 0:\n",
    "            n = len(matrix[0])\n",
    "        t,b,l,r = 0, m-1, 0, n-1\n",
    "        while t <= b and l <= r:\n",
    "            # right\n",
    "            for idx in range(l, r+1):\n",
    "                result.append(matrix[t][idx])\n",
    "            # down\n",
    "            for idx in range(t+1, b+1):\n",
    "                result.append(matrix[idx][r])\n",
    "            # left\n",
    "            if b > t:\n",
    "                for idx in range(r-1,l-1,-1):\n",
    "                    result.append(matrix[b][idx])\n",
    "            # up\n",
    "            if l < r:\n",
    "                for idx in range(b-1,t,-1):\n",
    "                    result.append(matrix[idx][l])\n",
    "            \n",
    "            t += 1\n",
    "            l += 1\n",
    "            b -= 1\n",
    "            r -= 1\n",
    "\n",
    "            # up\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        while matrix:\n",
    "            res += matrix.pop(0)\n",
    "            matrix = list(map(list, zip(*matrix)))[::-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        rows = len(matrix)\n",
    "        if rows == 0:\n",
    "            return []\n",
    "        cols = len(matrix[0])\n",
    "        start = 0\n",
    "        result = []\n",
    "\n",
    "        def print_num(start):\n",
    "            end_x = cols - 1- start\n",
    "            end_y = rows -1 - start\n",
    "            for i in range(start,end_x+1):\n",
    "                result.append(matrix[start][i])\n",
    "            if start<end_y:\n",
    "                for i in range(start+1,end_y+1):\n",
    "                    result.append(matrix[i][end_x])\n",
    "            \n",
    "            if start<end_y and start<end_x:\n",
    "                for i in range(end_x-1,start-1,-1):\n",
    "                    result.append(matrix[end_y][i])\n",
    "            \n",
    "            if start<end_y-1 and start<end_x:\n",
    "                for i in range(end_y-1,start,-1):\n",
    "                    result.append(matrix[i][start])\n",
    "            return\n",
    "\n",
    "        while rows >  start*2 and cols > start*2:\n",
    "            print_num(start)\n",
    "            start += 1\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        if not matrix:\n",
    "            return []\n",
    "        row, rows = 0, len(matrix)-1\n",
    "        col, cols = 0, len(matrix[0])-1\n",
    "        while col<=cols and row<=rows:\n",
    "            for j in range(col, cols+1):\n",
    "                res.append(matrix[row][j])\n",
    "            row += 1\n",
    "            for i in range(row, rows+1):\n",
    "                res.append(matrix[i][cols])\n",
    "            cols -= 1\n",
    "            if row<=rows:\n",
    "                for j in range(cols, col-1, -1):\n",
    "                    res.append(matrix[rows][j])\n",
    "            rows -= 1\n",
    "            if col<=cols:\n",
    "                for i in range(rows, row-1, -1):\n",
    "                    res.append(matrix[i][col])\n",
    "            col += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        # if not matrix: return matrix\n",
    "        # if len(matrix) ==1: return matrix[0]\n",
    "        \n",
    "        # begin,len_matrix,row = 0,len(matrix[0]),len(matrix)\n",
    "        # result=[]\n",
    "        # if len(matrix[0]) ==1:\n",
    "        #     for item in matrix:\n",
    "        #         result+=item\n",
    "        #     return result\n",
    "        # while len_matrix >0 and row >0 :\n",
    "        #     for i in range(begin,len_matrix-1):\n",
    "        #         result.append(matrix[begin][i])\n",
    "        #     for m in range(begin,row-1):\n",
    "        #         result.append(matrix[m][len_matrix-1])\n",
    "        #     for k in range(len_matrix-1,begin,-1):\n",
    "        #         result.append(matrix[row-1][k])\n",
    "        #     for j in range(row-1,begin,-1):\n",
    "        #         result.append(matrix[j][begin])\n",
    "        #     # print(result)    \n",
    "        #     begin +=1\n",
    "        #     len_matrix -=2\n",
    "        #     row -= 2\n",
    "        #     if len_matrix==1:\n",
    "        #         for i in range(begin,row):\n",
    "        #             result.append(matrix[i][begin])\n",
    "        #     if row == 1 : result+=matrix[begin][begin:len_matrix+1]\n",
    "        #     # if begin == row and begin == len_matrix: result.append(matrix[begin][begin])\n",
    "        # return result\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix: return []\n",
    "        NROW = len(matrix)\n",
    "        NCOL = len(matrix[0])\n",
    "        \n",
    "        def helper(depth):\n",
    "            nrow, ncol = NROW - 2 * depth, NCOL - 2 * depth\n",
    "            if nrow <= 0 or ncol <= 0: return []\n",
    "            if nrow == 1: return matrix[depth][depth:depth+ncol]\n",
    "            if ncol == 1: return [matrix[r][depth] for r in range(depth, depth + nrow)]\n",
    "\n",
    "            res = []\n",
    "            res += matrix[depth][depth:depth+ncol-1]\n",
    "            res += [matrix[r][depth+ncol-1] for r in range(depth, depth + nrow - 1)]\n",
    "            res += reversed(matrix[depth+nrow-1][depth+1:depth+ncol])\n",
    "            res += [matrix[r][depth] for r in reversed(range(depth +1, depth + nrow))]\n",
    "            return res + helper(depth + 1)\n",
    "            \n",
    "        return helper(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if len(matrix) == 0: return []\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        total = row * col\n",
    "        ans = []\n",
    "        l, r, t, b = 0, col - 1, 0, row - 1\n",
    "        while len(ans) < total:\n",
    "            # left to right\n",
    "            for i in range(l, r+1):\n",
    "                ans.append(matrix[t][i])\n",
    "            t += 1\n",
    "            if t-1 == b: continue # single row\n",
    "            # top to bottom\n",
    "            for i in range(t, b+1):\n",
    "                ans.append(matrix[i][r])\n",
    "            r -= 1\n",
    "            if r+1 == l: continue # single col\n",
    "            # right to left\n",
    "            for i in range(r, l-1, -1):\n",
    "                ans.append(matrix[b][i])\n",
    "            b -= 1\n",
    "            # bottom to top\n",
    "            for i in range(b, t-1, -1):\n",
    "                ans.append(matrix[i][l])\n",
    "            l += 1\n",
    "            #print(ans, l, r, t, b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix or not matrix[0]: return []\n",
    "        left, right, top, bottom = 0, len(matrix[0])-1, 0, len(matrix)-1\n",
    "        res = []\n",
    "        while left <= right and top <= bottom:\n",
    "            for i in range(left, right+1):\n",
    "                res.append(matrix[top][i])\n",
    "            top += 1\n",
    "            if top > bottom: break  # 防止只有一行的情况\n",
    "            for i in range(top, bottom+1):\n",
    "                res.append(matrix[i][right])\n",
    "            right -= 1\n",
    "            if right < left: break  # 防止只有一列的情况\n",
    "            for i in range(right, left-1, -1):\n",
    "                res.append(matrix[bottom][i])\n",
    "            bottom -= 1\n",
    "            for i in range(bottom, top-1, -1):\n",
    "                res.append(matrix[i][left])\n",
    "            left += 1\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        rest=len(matrix)*len(matrix[0])\n",
    "        d='right'\n",
    "        ans=[0]*rest\n",
    "        mark=[[True]*len(matrix[0]) for i in range(len(matrix))]\n",
    "        t=0\n",
    "        i=0\n",
    "        j=0\n",
    "        while t<rest:\n",
    "            print(\"i:{},j:{},t:{}\".format(i,j,t))\n",
    "            print(ans)\n",
    "            ans[t]=matrix[i][j]\n",
    "            mark[i][j]=False\n",
    "            t+=1\n",
    "            if d=='right':\n",
    "                if j==len(matrix[0])-1:\n",
    "                    d='down'\n",
    "                    i+=1\n",
    "                elif mark[i][j+1]==False:\n",
    "                    d='down'\n",
    "                    i+=1\n",
    "                else:\n",
    "                    j+=1\n",
    "            elif d=='down':\n",
    "                if i==len(matrix)-1:\n",
    "                    d='left'\n",
    "                    j-=1\n",
    "                elif mark[i+1][j]==False:\n",
    "                    d='left'\n",
    "                    j-=1\n",
    "                else:\n",
    "                    i+=1\n",
    "            elif d=='left':\n",
    "                if j==0:\n",
    "                    d='up'\n",
    "                    i-=1\n",
    "                elif mark[i][j-1]==False:\n",
    "                    d='up'\n",
    "                    i-=1\n",
    "                else:\n",
    "                    j-=1\n",
    "            elif d=='up':\n",
    "                if i==0:\n",
    "                    d='right'\n",
    "                    j+=1\n",
    "                elif mark[i-1][j]==False:\n",
    "                    d='right'\n",
    "                    j+=1\n",
    "                else:\n",
    "                    i-=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\r\n",
    "        if matrix is None:\r\n",
    "            return None\r\n",
    "        m = len(matrix)\r\n",
    "        n = len(matrix[0])\r\n",
    "\r\n",
    "        a = []\r\n",
    "\r\n",
    "        up = 0\r\n",
    "        down = m-1\r\n",
    "        left = 0\r\n",
    "        right = n-1\r\n",
    "\r\n",
    "        #>\r\n",
    "        while True:\r\n",
    "            a = a + matrix[up][left:right+1]\r\n",
    "            up += 1\r\n",
    "            if up > down: return a\r\n",
    "\r\n",
    "            #v\r\n",
    "            # a = a + matrix[up:down+1][right]\r\n",
    "            a = a + [row[right] for row in matrix[up:down+1]]\r\n",
    "            right -= 1\r\n",
    "            if left > right: return a\r\n",
    "\r\n",
    "            #<\r\n",
    "            a = a + matrix[down][left:right+1][::-1]\r\n",
    "            down -= 1\r\n",
    "            if up > down: return a\r\n",
    "\r\n",
    "            #^\r\n",
    "            # a = a + matrix[up:down+1][left][::-1]\r\n",
    "            a = a + [row[left] for row in matrix[up:down+1]][::-1]\r\n",
    "            left += 1\r\n",
    "            if left > right: return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        return matrix and list(matrix.pop(0)) + self.spiralOrder(list(zip(*matrix))[::-1])\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # 矩阵的旋转\n",
    "# class Solution:\n",
    "#     def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "#         res = []\n",
    "#         while matrix:\n",
    "#             res += matrix.pop(0)   # 始终弹出最上面的一行\n",
    "#             matrix = list(zip(*matrix))[::-1]  # 矩阵逆时针90旋转\n",
    "#         return res\n",
    "\n",
    "\n",
    "# 依次打印\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix: return []\n",
    "        left, right = 0, len(matrix[0]) - 1\n",
    "        top, bottom = 0, len(matrix) - 1\n",
    "        res = []\n",
    "        while matrix:\n",
    "            for i in range(left, right + 1):\n",
    "                res.append(matrix[top][i])    # 打印时某一行固定\n",
    "            top += 1                          # 行向下走\n",
    "            if top > bottom:   # 因为是打印某一行，所以上面行越过下面行就跳出\n",
    "                break\n",
    "            for i in range(top, bottom + 1):\n",
    "                res.append(matrix[i][right])\n",
    "            right -= 1\n",
    "            if left > right:\n",
    "                break\n",
    "            for i in range(right, left - 1, -1):    # 逆向，减一是为了包括进去0\n",
    "                res.append(matrix[bottom][i])\n",
    "            bottom -= 1\n",
    "            if top > bottom:\n",
    "                break\n",
    "            for i in range(bottom, top - 1, -1):\n",
    "                res.append(matrix[i][left])\n",
    "            left += 1\n",
    "            if left > right:\n",
    "                break\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n_row = len(matrix)\n",
    "        n_col = len(matrix[0])\n",
    "\n",
    "        res = []\n",
    "        for i in range(0, n_row // 2 + n_row % 2):\n",
    "            if i >= n_col // 2 + n_col % 2:\n",
    "                break\n",
    "            \n",
    "            if n_col-i > i:\n",
    "                for j in range(i, n_col-i):\n",
    "                    res.append(matrix[i][j])\n",
    "\n",
    "            if n_row-i > i+1:\n",
    "                for j in range(i+1, n_row-i):\n",
    "                    res.append(matrix[j][n_col-1-i])\n",
    "\n",
    "            if n_row-1-i > i and n_col-1-i > i:\n",
    "                for j in range(n_col-2-i, i-1, -1):\n",
    "                    res.append(matrix[n_row-1-i][j])\n",
    "\n",
    "            if n_row-1-i > i and n_col-1-i > i:\n",
    "                for j in range(n_row-2-i, i, -1):\n",
    "                    res.append(matrix[j][i])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix):\n",
    "        res = []\n",
    "\n",
    "        # 用四个变量代表四个方向\n",
    "        direc = 0\n",
    "        x, y = 0, 0\n",
    "        res.append(matrix[x][y])\n",
    "\n",
    "        # 在一个方向添加元素\n",
    "        while (len(res) < len(matrix[0]) * len(matrix)):\n",
    "            if direc % 4 == 0:\n",
    "                if y < (len(matrix[0]) - (direc // 4 + 1)):\n",
    "                    y = y + 1\n",
    "                    res.append(matrix[x][y])\n",
    "                else:\n",
    "                    direc = direc + 1\n",
    "            elif direc % 4 == 1:\n",
    "                if x < (len(matrix) - (direc // 4 + 1)):\n",
    "                    x = x + 1\n",
    "                    res.append(matrix[x][y])\n",
    "                else:\n",
    "                    direc = direc + 1\n",
    "            elif direc % 4 == 2:\n",
    "                if y > direc // 4:\n",
    "                    y = y - 1\n",
    "                    res.append(matrix[x][y])\n",
    "                else:\n",
    "                    direc = direc + 1\n",
    "            else:\n",
    "                if x > (direc // 4 + 1):\n",
    "                    x = x - 1\n",
    "                    res.append(matrix[x][y])\n",
    "                else:\n",
    "                    direc = direc + 1\n",
    "\n",
    "        return res\n",
    "                \n",
    "                  \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        def dfs(i,j,cur):\n",
    "            if i<0 or i>=m or j<0 or j>=n or visited[i][j]==1:\n",
    "                return\n",
    "            ans.append(matrix[i][j])\n",
    "            visited[i][j] = 1\n",
    "\n",
    "            di,dj = directions[cur%4]\n",
    "            dfs(i+di,j+dj,cur)\n",
    "\n",
    "            cur +=1\n",
    "            di,dj = directions[cur%4]\n",
    "            dfs(i+di,j+dj,cur)\n",
    "\n",
    "        i,j = 0,0\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        visited =[ [0 for _ in range(n)] for _ in range(m)]\n",
    "        ans = []\n",
    "        cur = 0\n",
    "        directions = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "\n",
    "        dfs(i,j,cur)\n",
    "        return(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        outlist = [matrix[0][0]]\n",
    "        matrix[0][0] = 101\n",
    "        x, y = 0, 0\n",
    "        direction = 0\n",
    "        for _ in range(m * n + 4 * m + 4 * n):\n",
    "            print(x, y, direction)\n",
    "            if direction == 0:  # right\n",
    "                if y + 1 in range(n):\n",
    "                    if matrix[x][y + 1] != 101:\n",
    "                        outlist.append(matrix[x][y + 1])\n",
    "                        matrix[x][y + 1] = 101\n",
    "                        y += 1\n",
    "                    else:\n",
    "                        direction = 1\n",
    "                else:\n",
    "                    direction = 1\n",
    "\n",
    "            elif direction == 1:  # down\n",
    "                if x + 1 in range(m):\n",
    "                    if matrix[x + 1][y] != 101:\n",
    "                        outlist.append(matrix[x + 1][y])\n",
    "                        matrix[x + 1][y] = 101\n",
    "                        x += 1\n",
    "                    else:\n",
    "                        direction = 2\n",
    "                else:\n",
    "                    direction = 2\n",
    "\n",
    "            elif direction == 2:  # left\n",
    "                if y - 1 in range(n):\n",
    "                    if matrix[x][y - 1] != 101:\n",
    "                        outlist.append(matrix[x][y - 1])\n",
    "                        matrix[x][y - 1] = 101\n",
    "                        y -= 1\n",
    "                    else:\n",
    "                        direction = 3\n",
    "                else:\n",
    "                    direction = 3\n",
    "\n",
    "            elif direction == 3:  # up\n",
    "                if x - 1 in range(m):\n",
    "                    if matrix[x - 1][y] != 101:\n",
    "                        outlist.append(matrix[x - 1][y])\n",
    "                        matrix[x - 1][y] = 101\n",
    "                        x -= 1\n",
    "                    else:\n",
    "                        direction = 0\n",
    "                else:\n",
    "                    direction = 0\n",
    "\n",
    "        return outlist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix or not matrix[0]:return []\n",
    "        row,col=len(matrix),len(matrix[0])\n",
    "        res=[]\n",
    "        left,right,top,bot=0,col-1,0,row-1\n",
    "        while left<=right and top<=bot:\n",
    "            for i in range(left,right+1):\n",
    "                res.append(matrix[top][i])\n",
    "            for j in range(top+1,bot+1):\n",
    "                res.append(matrix[j][right])\n",
    "            if left < right and top < bot:\n",
    "                for column in range(right - 1, left, -1):\n",
    "                    res.append(matrix[bot][column])\n",
    "                for row in range(bot, top, -1):\n",
    "                    res.append(matrix[row][left])\n",
    "            left+=1\n",
    "            right-=1\n",
    "            top+=1\n",
    "            bot-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "\n",
    "        lb, ub, rb, db = 0, 0, len(matrix[0])-1, len(matrix)-1\n",
    "        ans = []\n",
    "        while lb<=rb and ub<=db:\n",
    "            for col in range(lb, rb):\n",
    "                ans.append(matrix[ub][col])\n",
    "            for row in range(ub, db+1):\n",
    "                ans.append(matrix[row][rb])\n",
    "            \n",
    "            if lb<rb and ub<db:\n",
    "                for col in range(rb-1, lb-1, -1):\n",
    "                    ans.append(matrix[db][col])\n",
    "                for row in range(db-1, ub, -1):\n",
    "                    ans.append(matrix[row][lb])\n",
    "            lb += 1\n",
    "            ub += 1\n",
    "            rb -= 1\n",
    "            db -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return list()\n",
    "        \n",
    "        rows, columns = len(matrix), len(matrix[0])\n",
    "        visited = [[False] * columns for _ in range(rows)]\n",
    "        total = rows * columns\n",
    "        order = [0] * total\n",
    "\n",
    "        directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        row, column = 0, 0\n",
    "        directionIndex = 0\n",
    "        for i in range(total):\n",
    "            order[i] = matrix[row][column]\n",
    "            visited[row][column] = True\n",
    "            nextRow, nextColumn = row + directions[directionIndex][0], column + directions[directionIndex][1]\n",
    "            if not (0 <= nextRow < rows and 0 <= nextColumn < columns and not visited[nextRow][nextColumn]):\n",
    "                directionIndex = (directionIndex + 1) % 4\n",
    "            row += directions[directionIndex][0]\n",
    "            column += directions[directionIndex][1]\n",
    "        return order"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
